package com.yiguang.algorithm.string;


// 题目：14、28
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.alibaba.fastjson.JSON;

public class Solution {
	
	public static void main(String[] args) {
		Solution solution = new Solution();
		/*
		String[] strs = {"flower","flow","flight"};
		String result = solution.longestCommonPrefix(strs);
		System.out.println(result);
		
		int index = solution.strStr("mississippi", "issipi");
		System.out.println(index);
		*/
		String[] words = {"bar","foo","the"};
		System.out.println(Solution.findSubstring("barfoofoobarthefoobarman",words));
		
	}
	
	/*
	4. 寻找两个正序数组的中位数
	给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
	进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
	*/
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		
		return 2.23;
    }
	
	/*
	8.请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

	函数 myAtoi(string s) 的算法如下：

	读入字符串并丢弃无用的前导空格
	检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
	读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
	将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
	如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
	返回整数作为最终结果。
	注意：

	本题中的空白字符只包括空格字符 ' ' 。
	除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
	 

	示例 1：

	输入：s = "42"
	输出：42
	解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
	第 1 步："42"（当前没有读入字符，因为没有前导空格）
	         ^
	第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
	         ^
	第 3 步："42"（读入 "42"）
	           ^
	解析得到整数 42 。
	由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
	示例 2：

	输入：s = "   -42"
	输出：-42
	解释：
	第 1 步："   -42"（读入前导空格，但忽视掉）
	            ^
	第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
	             ^
	第 3 步："   -42"（读入 "42"）
	               ^
	解析得到整数 -42 。
	由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
	示例 3：

	输入：s = "4193 with words"
	输出：4193
	解释：
	第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
	         ^
	第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
	         ^
	第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
	             ^
	解析得到整数 4193 。
	由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
	示例 4：

	输入：s = "words and 987"
	输出：0
	解释：
	第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
	         ^
	第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
	         ^
	第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
	         ^
	解析得到整数 0 ，因为没有读入任何数字。
	由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0 。
	示例 5：

	输入：s = "-91283472332"
	输出：-2147483648
	解释：
	第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
	         ^
	第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
	          ^
	第 3 步："-91283472332"（读入 "91283472332"）
	                     ^
	解析得到整数 -91283472332 。
	由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -231 = -2147483648 。

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/string-to-integer-atoi
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	*/
	public static int myAtoi(String s) {
		String result = "";
		boolean blank = true;
        // 1.转换为-+和数字
		for(int i=0; i<s.length(); i++) {
			char index = s.charAt(i);
            // 处理空格
			if(index==' '&&blank==true) {
				continue;
			}else {
				if(Character.isDigit(index)) {
					result+=index;
					blank=false;
				}else {
                    // 处理-+
                    if ((index=='-'|| index=='+')&&blank==true) {
                    	result+=index;
                    	blank=false;
                    	continue;
                    }
					break;
				}
				
			}
		}
		if(result.equals("") || result.equals("-") || result.equals("+")) {
            return 0;
        }
		System.out.println(result);
        // 2.处理长度大于long的极限
		if(result.length()>12&&result.contains("-")) {
			while(result.charAt(1)=='0') {
				result=result.replaceFirst("0", "");
                if(result.length()==1) {
				    return 0;
			    }
			}
			if(result.length()>12&&result.contains("-")) {
				return Integer.MIN_VALUE;
			}
			
		}else if (result.length()>12&&result.contains("+")){
			while(result.charAt(1)=='0') {
				result=result.replaceFirst("0", "");
				System.out.println(result);
                if(result.length()==0) {
				    return 0;
			    }
			}
			if(result.length()>12) {
				return Integer.MAX_VALUE;
			}
			
		}else if (result.length()>12){
			while(result.charAt(0)=='0') {
				result=result.replaceFirst("0", "");
				System.out.println(result);
                if(result.length()==0) {
				    return 0;
			    }
			}
			if(result.length()>12) {
				return Integer.MAX_VALUE;
			}
		}
		// 3.处理为int的极限
		if(Long.valueOf(Integer.MIN_VALUE)>Long.valueOf(result)) {
			result = String.valueOf(Integer.MIN_VALUE);
		}else if(Long.valueOf(Integer.MAX_VALUE)<Long.valueOf(result)){
			result = String.valueOf(Integer.MAX_VALUE);
		}
		return Integer.valueOf(result);
    }
	
	/*
	14. 最长公共前缀
	编写一个函数来查找字符串数组中的最长公共前缀。
	如果不存在公共前缀，返回空字符串 ""。
	*/
	public String longestCommonPrefix(String[] strs) {
		String comment = "";
		for(int i=0; i<strs.length; i++) {
			String index = strs[i];
			if(i==0) {
				comment = index;
				continue;
			}
			String current = comment;
			comment = "";
			char[] currentChar = current.toCharArray();
			char[] indexChar = index.toCharArray();
			if(currentChar.length>indexChar.length) {
				a:for(int j=0; j<indexChar.length; j++) {
					if(currentChar[j]==indexChar[j]) {
						comment = comment+currentChar[j];
					}else {
						break a;
					}
				}
			}else {
				a:for(int j=0; j<currentChar.length; j++) {
					if(currentChar[j]==indexChar[j]) {
						comment = comment+currentChar[j];
					}else {
						break a;
					}
				}
			}
			
			System.out.println(i+":"+comment);
		}
		return comment;
    }
	
	/*
	17.给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

	给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
	示例 1：

	输入：digits = "23"
	输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
	示例 2：

	输入：digits = ""
	输出：[]
	示例 3：

	输入：digits = "2"
	输出：["a","b","c"]

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
	public List<String> letterCombinations(String digits) {
		Map<Integer, List<String>> phone = new HashMap();
		phone.put(2, Arrays.asList("a","b","c"));
		phone.put(3, Arrays.asList("d","e","f"));
		phone.put(4, Arrays.asList("g","h","i"));
		phone.put(5, Arrays.asList("j","k","l"));
		phone.put(6, Arrays.asList("m","n","o"));
		phone.put(7, Arrays.asList("p","q","r","s"));
		phone.put(8, Arrays.asList("t","u","v"));
		phone.put(9, Arrays.asList("w","x","y","z"));
		
		Map<Integer, ArrayList> results = new HashMap();
		char[] digitsArr = digits.toCharArray();
		if(digitsArr.length==0) {
			return new ArrayList();
		}
		for(int i=0; i<digitsArr.length; i++) {
			ArrayList result = new ArrayList();
			results.put(i, result);
		}
		for(int i=0; i<digits.length(); i++) {
			char element = digitsArr[i];
			ArrayList<String> result = results.get(i);
			ArrayList<String> preResult = results.get(i-1);
			System.out.println(Integer.valueOf(String.valueOf(element)));
			List<String> phones = phone.get(Integer.valueOf(String.valueOf(element)));
			System.out.println("phones:"+JSON.toJSONString(phones));
			if(i==0) {
				for(String ele :phones) {
					result.add(ele);
				}
			}else {
				for(String pre:preResult) {
					for(String ele:phones) {
						result.add(pre+ele);
					}
				}
			}
		}
		for(int i=0; i<digits.length(); i++) {
			System.out.println(i+":"+results.get(i).size());
			System.out.println(JSON.toJSONString(results.get(i)));
		}
		System.out.println(results.get(digits.length()-1));
		return results.get(digits.length()-1);
    }
	
	/*
	28.实现 strStr() 函数。
	给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
	说明：
	当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
	对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
	*/
	public int strStr(String haystack, String needle) {
		if(needle.length()==0) {
			return 0;
		}
		if(needle.length()>haystack.length()) {
			return -1;
		}
		char[] haystacks = haystack.toCharArray();
		char[] needles = needle.toCharArray();
		for(int i=0; i<haystacks.length; i++) {
			int m=i;
			int j=0;
			System.out.println(i);
			while(haystacks[m]==needles[j]) {
				if(j+1==needles.length) {
					return i;
				}
				++m;
				if(m==haystacks.length) {
					return -1;
				}
				++j;
			}
			
		}
		return -1;

    }
	
	/*
	30. 串联所有单词的子串
	给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
	注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
	*/
	public static List<Integer> findSubstring(String s, String[] words) {
		// s = "barfoobarfoobarfoo", words = ["foo","bar"]
		// "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
		// s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
		// String source = "pjzkrkevzztxductzzxmxsvwjkxpvukmfjywwetvfnujhweiybwvvsrfequzkhossmootkmyxgjgfordrpapjuunmqnxxdrqrfgkrsjqbszgiqlcfnrpjlcwdrvbumtotzylshdvccdmsqoadfrpsvnwpizlwszrtyclhgilklydbmfhuywotjmktnwrfvizvnmfvvqfiokkdprznnnjycttprkxpuykhmpchiksyucbmtabiqkisgbhxngmhezrrqvayfsxauampdpxtafniiwfvdufhtwajrbkxtjzqjnfocdhekumttuqwovfjrgulhekcpjszyynadxhnttgmnxkduqmmyhzfnjhducesctufqbumxbamalqudeibljgbspeotkgvddcwgxidaiqcvgwykhbysjzlzfbupkqunuqtraxrlptivshhbihtsigtpipguhbhctcvubnhqipncyxfjebdnjyetnlnvmuxhzsdahkrscewabejifmxombiamxvauuitoltyymsarqcuuoezcbqpdaprxmsrickwpgwpsoplhugbikbkotzrtqkscekkgwjycfnvwfgdzogjzjvpcvixnsqsxacfwndzvrwrycwxrcismdhqapoojegggkocyrdtkzmiekhxoppctytvphjynrhtcvxcobxbcjjivtfjiwmduhzjokkbctweqtigwfhzorjlkpuuliaipbtfldinyetoybvugevwvhhhweejogrghllsouipabfafcxnhukcbtmxzshoyyufjhzadhrelweszbfgwpkzlwxkogyogutscvuhcllphshivnoteztpxsaoaacgxyaztuixhunrowzljqfqrahosheukhahhbiaxqzfmmwcjxountkevsvpbzjnilwpoermxrtlfroqoclexxisrdhvfsindffslyekrzwzqkpeocilatftymodgztjgybtyheqgcpwogdcjlnlesefgvimwbxcbzvaibspdjnrpqtyeilkcspknyylbwndvkffmzuriilxagyerjptbgeqgebiaqnvdubrtxibhvakcyotkfonmseszhczapxdlauexehhaireihxsplgdgmxfvaevrbadbwjbdrkfbbjjkgcztkcbwagtcnrtqryuqixtzhaakjlurnumzyovawrcjiwabuwretmdamfkxrgqgcdgbrdbnugzecbgyxxdqmisaqcyjkqrntxqmdrczxbebemcblftxplafnyoxqimkhcykwamvdsxjezkpgdpvopddptdfbprjustquhlazkjfluxrzopqdstulybnqvyknrchbphcarknnhhovweaqawdyxsqsqahkepluypwrzjegqtdoxfgzdkydeoxvrfhxusrujnmjzqrrlxglcmkiykldbiasnhrjbjekystzilrwkzhontwmehrfsrzfaqrbbxncphbzuuxeteshyrveamjsfiaharkcqxefghgceeixkdgkuboupxnwhnfigpkwnqdvzlydpidcljmflbccarbiegsmweklwngvygbqpescpeichmfidgsjmkvkofvkuehsmkkbocgejoiqcnafvuokelwuqsgkyoekaroptuvekfvmtxtqshcwsztkrzwrpabqrrhnlerxjojemcxel";
		// String[] arrs = {"dhvf","sind","ffsl","yekr","zwzq","kpeo","cila"};
		String source = s;
		String[] arrs = words;
		Map<Integer,ArrayList<String>> results = new HashMap();
		Map<Integer,ArrayList> indexs = new HashMap();
		for(int i=0; i<arrs.length; i++) {
			results.put(i, new ArrayList());
			indexs.put(i, new ArrayList());
		}
		Set<Integer> keys = results.keySet();
		Iterator<Integer> iter = keys.iterator();
		while(iter.hasNext()) {
			Integer key = iter.next();
			ArrayList<String> result = results.get(key);
			ArrayList<String> preResult = results.get(key-1);
			ArrayList index = indexs.get(key);
			ArrayList preIndex = indexs.get(key-1);
			if(key==0) {
				for(int j=0; j<arrs.length; j++) {
					if(!result.contains(arrs[j])) {
						List<Integer> cur = new ArrayList();
						result.add(arrs[j]);
						cur.add(j);
						index.add(cur);
					}
				}
			} else{
				for(int k=0; k<preResult.size(); k++) {
					String element = preResult.get(k);
					ArrayList preCur = (ArrayList) preIndex.get(k);
					for(int j=0; j<arrs.length; j++) {
						if(!preCur.contains(j)&&!result.contains(element+arrs[j])) {
							List<Integer> cur = new ArrayList();
							result.add(element+arrs[j]);
							cur.addAll(preCur);
							cur.add(j);
							index.add(cur);
						}
					}
					
				}
			}
			System.out.println(key);
			System.out.println(results.get(key).size());
			System.out.println(JSON.toJSONString(results.get(key)));
			System.out.println(JSON.toJSONString(result));
			System.out.println(JSON.toJSONString(index));
		}
		for(int i=0; i<arrs.length; i++) {
			System.out.println(results.get(i).size());
			System.out.println(JSON.toJSONString(results.get(i)));
		}
		List<String> all = results.get(arrs.length-1);
		List<Integer> allIndex = new ArrayList();
		for(String combo:all) {
			for(int i=0; i<source.length(); i++) {
				Integer index = source.indexOf(combo, i);
				if(index>=0) {
					if(!allIndex.contains(index)) {
						allIndex.add(index);
					}
					
				}
			}
		}
		System.out.println(JSON.toJSONString(allIndex));
		return allIndex;
	}
	
	/*
	26.给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

	不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

	 

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
	
	public int removeDuplicates(int[] nums) {
		int newLength = 0;
		for(int i=0; i<nums.length; i++) {
			int current = nums[i];
			if(i==0) {
				++newLength;
				continue;
			}
			for(int j=0; j<newLength; j++) {
				int element = nums[j];
				if(element==current) {
					break;
				}
				if(j==newLength-1) {
					nums[newLength]=nums[i];
					++newLength;
					
				}
			}
		}
		System.out.println(JSON.toJSONString(nums));
		return newLength;
    }
	
	/*
	27.给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

	不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

	元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/remove-element
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
	public int removeElement(int[] nums, int val) {
        int count = 0;
        for(int i=0; i<nums.length; i++) {
            if(nums[i]!=val) {
                nums[count]=nums[i];
                count++;
            }
            System.out.println(JSON.toJSONString(nums));
        }
        return count;
    }
	

}
